import { bTree } from './构建二叉树.js'


/*

            3
          /   \
         1     8
        / \   / 
       0   2  5 
              \
               7
              /
             6  

*/
// 前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）
// 前序遍历结果： [3, 1, 0, 2, 8, 5, 7, 6]

/** 递归 */
var preorderTraversal = function(root, array = []) {
    if (root) {
        array.push(root.data);
        preorderTraversal(root.left, array);
        preorderTraversal(root.right, array);
    }
    return array;
};

// 测试递归
var pt = preorderTraversal(bTree.root)
console.log('递归遍历结果：')
console.log(pt)

/** 非递归 */
/**
 * 取跟结点作为当前结点，开始遍历
 * 1. 访问根结点
 * 2. 左孩子依次入栈，直到左孩子为空的结点
 * 3. 结点出栈，以右孩子为当前结点，再依次执行步骤1、2、3
 */
var preorderTraversal = function(root) {
    const result = [];
    const stack = [];
    let current = root;
    while (current || stack.length > 0) {
        while (current) {
            result.push(current.data);
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        current = current.right;
    }
    return result;
};

// 测试非递归
var pt = preorderTraversal(bTree.root)
console.log('非递归遍历结果：')
console.log(pt)